package leetcode.code0803;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

// 16:24:26 - 17:38
public class Solution implements IDebug {

	int[][] grid;
	int[][] hits;
	int m, n;// grid 长和宽
	int h;// hits的长度

	public int[] hitBricks(int[][] grid, int[][] hits) {
		this.grid = grid;
		this.hits = hits;
		this.m = grid.length;
		this.n = grid[0].length;
		this.h = hits.length;
		this.hit();// 粘炮弹
		Union union = new Union(this.grid, m, n);
		int[] ans = new int[this.h];
		int ceilingNum = union.ceilingNum;
		for (int i = this.h - 1; i >= 0; i--) {
			int x = hits[i][0], y = hits[i][1];
			if (this.grid[x][y] == 2) {
				union.boom(x, y);
				int cur = union.ceilingNum;
				ans[i] = cur - ceilingNum - 1;
				ceilingNum = cur;
			} else {
				ans[i] = 0;// 假设两炮不会打到同一个位置
			}
		}
		return ans;
	}

	// 炮弹把能打的1打断
	private void hit() {
		for (int i = 0; i < this.h; i++) {
			int x = this.hits[i][0], y = this.hits[i][1];
			if (this.grid[x][y] == 1) {
				this.grid[x][y] = 2;
			}
		}
	}

	class Union {

		private int m;
		private int n;
		private int gridNum;
		private int[] head;// 头
		private int[] sizes;// 集合size
		private boolean[] isCeiling;// 是否是天棚节点
		private int[] stack;
		private int pstack;
		int ceilingNum;// 粘在天花板上的方块数量
		int[][] grid;

		public Union(int[][] grid, int m, int n) {
			this.grid = grid;
			this.m = m;
			this.n = n;
			this.gridNum = m * n;
			this.head = new int[this.gridNum];
			this.sizes = new int[this.gridNum];
			this.isCeiling = new boolean[this.gridNum];
			this.stack = new int[this.gridNum];
			this.ceilingNum = 0;
			this.initHead();
			this.initUnion();
		}

		public void boom(int x, int y) {
			int index = this.index(x, y);
			this.grid[x][y] = 1;
			if (x == 0) {
				this.isCeiling[index] = true;
				this.ceilingNum++;
			}
			this.union(x, y, x + 1, y);
			this.union(x, y, x - 1, y);
			this.union(x, y, x, y + 1);
			this.union(x, y, x, y - 1);
		}

		// union沾着炮弹的原始数组
		private void initUnion() {
			// 第一行，紧接着天棚的一行
			for (int j = 1; j < n; j++) {
				this.union(0, j, 0, j - 1);
			}
			// 第一列
			for (int i = 1; i < m; i++) {
				this.union(i, 0, i - 1, 0);
			}
			// 其它行列
			for (int i = 1; i < m; i++) {
				for (int j = 1; j < n; j++) {
					this.union(i, j, i - 1, j);
					this.union(i, j, i, j - 1);
				}
			}
		}

		private void union(int r1, int c1, int r2, int c2) {
			if (this.check(r1, c1) && this.check(r2, c2)) {
				int h1 = this.findHead(r1, c1);
				int h2 = this.findHead(r2, c2);
				if (h1 != h2) {
					int size1 = this.sizes[h1];
					int size2 = this.sizes[h2];
					if (size1 < size2) {
						this.head[h1] = h2;
						this.sizes[h1] = 0;
						this.sizes[h2] = size1 + size2;
					} else {
						this.head[h2] = h1;
						this.sizes[h2] = 0;
						this.sizes[h1] = size1 + size2;
					}
					this.updateCeilingNum(h1, size1, h2, size2);
				}
			}
		}

		private boolean check(int r, int c) {
			if (r < 0 || r >= m || c < 0 || c >= n || this.grid[r][c] != 1) {
				return false;
			}
			return true;
		}

		// 更新天棚方块总数
		private void updateCeilingNum(int h1, int size1, int h2, int size2) {
			boolean b1 = this.isCeiling[h1];
			boolean b2 = this.isCeiling[h2];
			if (!b1 && b2) {
				this.isCeiling[h1] = true;
				this.ceilingNum += size1;
			} else if (b1 && !b2) {
				this.isCeiling[h2] = true;
				this.ceilingNum += size2;
			}
		}

		private int findHead(int r1, int c1) {
			int index = this.index(r1, c1);
			this.pstack = -1;
			int ans = index;
			while ((ans = this.head[index]) != index) {
				this.stack[++this.pstack] = index;
				index = ans;
			}
			while (this.pstack > -1) {
				this.head[this.stack[this.pstack--]] = ans;
			}
			return ans;
		}

		private void initHead() {
			// 初始化天棚节点
			for (int j = 0; j < n; j++) {
				int index = this.index(0, j);
				this.head[index] = index;
				this.sizes[index] = 1;
				if (this.grid[0][j] == 1) {// 方块贴在天棚上
					this.ceilingNum++;
					this.isCeiling[index] = true;
				}
			}
			// 初始化其它节点
			for (int i = 1; i < m; i++) {
				for (int j = 0; j < n; j++) {
					int index = this.index(i, j);
					this.head[index] = index;
					this.sizes[index] = 1;
					this.isCeiling[index] = false;
				}
			}
		}

		// 二维坐标转一维坐标
		public int index(int r, int c) {
			return r * n + c;
		}

	}

	@Override
	public void debug1() {
		int[] e = HelpDebug.str2array3("[2]");
		HelpDebug.compare(e, this.hitBricks(HelpDebug.str2array1("[[1,0,0,0],[1,1,1,0]]"), HelpDebug.str2array1("[[1,0]]")));
	}

	@Override
	public void debug2() {
		int[] e = HelpDebug.str2array3("[0,0]");
		HelpDebug.compare(e, this.hitBricks(HelpDebug.str2array1("[[1,0,0,0],[1,1,0,0]]"), HelpDebug.str2array1("[[1,1],[1,0]]")));
	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
